//<p>给你一个字符串 <code>s</code>，找到 <code>s</code> 中最长的回文子串。</p>
//
//<p> </p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = "babad"
//<strong>输出：</strong>"bab"
//<strong>解释：</strong>"aba" 同样是符合题意的答案。
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = "cbbd"
//<strong>输出：</strong>"bb"
//</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = "a"
//<strong>输出：</strong>"a"
//</pre>
//
//<p><strong>示例 4：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = "ac"
//<strong>输出：</strong>"a"
//</pre>
//
//<p> </p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 <= s.length <= 1000</code></li>
//	<li><code>s</code> 仅由数字和英文字母（大写和/或小写）组成</li>
//</ul>
//<div><div>Related Topics</div><div><li>字符串</li><li>动态规划</li></div></div><br><div><li>👍 3997</li><li>👎 0</li></div>
package leetcode.editor.cn;

//Java：最长回文子串
public class LongestPalindromicSubstring_5 {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring_5().new Solution();
        // TO TEST
        //System.out.println(solution.longestPalindrome("babad").equals("bab"));
        System.out.println(solution.longestPalindrome("cbbd").equals("bb"));
        System.out.println(solution.longestPalindrome("cbabd").equals("bab"));
        System.out.println(solution.longestPalindrome("cbaabd").equals("baab"));
    }

    /**
     * 第一种方式
     * 使用滑动窗口缩减的方式，然后暴力对比
     * 第二方式 这种新能查
     * 使用滑动窗口缩减的方式，然后使用字符串翻转，在对比
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            int strLen = s.length();
            for (int winLen = strLen; winLen > 1; winLen--) {
                int len = strLen - winLen;
                for (int k = 0; k <= len; k++) {
                    int start = k;
                    int end = start + winLen - 1;
                    while (s.charAt(start) == s.charAt(end)) {
                        start++;
                        end--;
                        if (start >= end) {
                            return s.substring(k, k + winLen);
                        }
                    }
                }
            }
            return s.substring(0, 1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}